package offer;

import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhanBo
 * @date 2020/5/25
 */
public class Solution55 {

    public static void main(String[] args) {

    }

    /**
     * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，
     * 最长路径的长度为树的深度
     *
     * 给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3 。
     *树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，本文使用递归实现。
     * 关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1+1 。
     *
     * 算法解析：
     * 终止条件： 当 root​ 为空，说明已越过叶节点，因此返回 深度 00 。
     * 递推工作： 本质上是对树做后序遍历。
     *      计算节点 root​ 的 左子树的深度 ，即调用 maxDepth(root.left)；
     *      计算节点 root​ 的 右子树的深度 ，即调用 maxDepth(root.right)；
     * 返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 层序遍历（BFS）
     *
     * 树的层序遍历 / 广度优先搜索往往利用 队列 实现。
     * 关键点： 每遍历一层，则计数器 +1+1 ，直到遍历完成，则可得到树的深度。
     * 算法解析：
         * 特例处理： 当 root​ 为空，直接返回 深度 00 。
         * 初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
         * 循环遍历： 当 queue 为空时跳出。
             * 初始化一个空列表 tmp ，用于临时存储下一层节点；
             * 遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp；
             * 更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue；
             * 统计层数： 执行 res += 1 ，代表层数加 11；
         * 返回值： 返回 res 即可。
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        List<TreeNode> queue = new LinkedList<>();
        List<TreeNode> tmp ;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) {
                    tmp.add(node.left);
                }
                if(node.right != null) {
                    tmp.add(node.right);
                }
            }
            queue = tmp;
            res++;
        }
        return res;
    }


    /**
     * 剑指 Offer 55 - II. 平衡二叉树
     *
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，
     * 那么它就是一棵平衡二叉树。
     *
     * 返回值： 若 recur(root) != -1 ，则说明此树平衡，返回 truetrue ； 否则返回 falsefalse 。
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    /**
     * 返回值：
         * 当节点root 左 / 右子树的深度差 \leq 1≤1 ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值 +1+1
         *      （ max(left, right) + 1 ）；
         * 当节点root 左 / 右子树的深度差 > 2>2 ：则返回 -1−1 ，代表 此子树不是平衡树 。
     * 终止条件：
         * 当 root 为空：说明越过叶节点，因此返回高度 00 ；
         * 当左（右）子树深度为 -1−1 ：代表此树的 左（右）子树 不是平衡树，因此剪枝，直接返回 -1−1 ；
     * @param root
     * @return
     */
    private int recur(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //左子树的高度
        int left = recur(root.left);
        //不平衡
        if(left == -1) {
            return -1;
        }
        //右子树的高度
        int right = recur(root.right);
        //不平衡
        if(right == -1) {
            return -1;
        }
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }





}
